package leetcode_day._2021._202106._0110;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/6/2 22:06
 * 连续的子数组和
 * 算法：前缀和
 * 假设 pre 是数组的前缀和，[i, j] 满足条件
 * [i, j] 的和为 (pre[j + 1] - pre[i]) % k = n
 * pre[j + 1] % k == pre[i] % k
 */
public class _02_523 {
    public static void main(String[] args) {
        System.out.println(new _02_523().checkSubarraySum(new int[]{23, 2, 6, 4, 7}, 13));
    }

    public boolean checkSubarraySum(int[] nums, int k) {
        int m = nums.length;
        if (m < 2) return false;
        int[] sum = new int[m + 1];
        for (int i = 1; i <= m; i++) sum[i] = sum[i - 1] + nums[i - 1];
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        for (int i = 1; i <= m; i++) {
            int tmp = sum[i] % k;
            if (map.containsKey(tmp)) {
                if (i - map.get(tmp) - 1 >= 2) return true;
            } else map.put(tmp, i - 1);
        }
        return false;
    }

}
